package exercises.newcoder.solution;

/**
 * <a href="https://www.nowcoder.com/practice/bb1615c381cc4237919d1aa448083bcc?tpId=188&&tqId=38606&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking">
 * NC149 kmp算法</a>
 *
 * @author or2
 * @Description 描述
 * 给你一个文本串S，一个非空模板串T，问S在T中出现了多少次
 * <p>
 * 数据范围：
 * 1 \le len(S) \le 5*10^5, 1 \le len(T) \le 10^61≤len(S)≤5∗10
 * 5
 * ,1≤len(T)≤10
 * 6
 * <p>
 * <p>
 * 复杂度要求：
 * O(n \cdot m) \O(n⋅m)
 * @create 2021年09月02日 时间: 11:22
 */
public class KMP {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * <p>
     * 计算模板串S在文本串T中出现了多少次
     *
     * @param S string字符串 模板串
     * @param T string字符串 文本串
     * @return int整型
     */
    public int kmp(String S, String T) {
        char[] tToCharArray = T.toCharArray();
        char[] sToCharArray = S.toCharArray();
        int[] nextArray = getNextArray(sToCharArray);
//        答案变量
        int ans = 0;

//        匹配 文本串的指针
        int j = 0;
        for (int i = 0; i < tToCharArray.length; i++) {
//            匹配上了, 继续下一个
            if (tToCharArray[i] == sToCharArray[j]) {
                j++;
//                若全部匹配完成, 则进入下一轮
                if (j == sToCharArray.length) {
                    ans++;
                    j = nextArray[j];
                }
            } else {
//                没匹配上, 当前字符(i--)继续匹配最长前缀下一字符
                if (nextArray[j] != -1) {
                    j = nextArray[j];
                    i--;
                }
            }
        }
        return ans;
    }

    /**
     * 最优子解 - 动态规划
     *
     * @param chars 原字符串
     * @return 原字符串的 最长前缀匹配数组
     */
    private int[] getNextArray(char[] chars) {
//        最后 +1 包含了全部字串的最长前缀, 仅匹配一次的话无需使用
        int length = chars.length + 1;
        int[] next = new int[length];

        next[0] = -1;
        next[1] = 0;
        for (int i = 2; i < length; i++) {
            int match = next[i - 1] + 1;
            while (match > 0) {
//                最长前缀, 同当前字符无关, i-1
                if (chars[i - 1] == chars[match]) {
                    next[i] = match;
                    break;
                } else {
                    int nextMatch = next[i - 1];
                    match = next[nextMatch] + 1;
                }
            }
            if (match == 0) {
                next[i] = 0;
            }
        }

        return next;
    }
}